The present invention relates to communication networks, and more particularly, to methods for minimizing collisions, frame-delivery latency and frame-delivery latency jitter in a network.
Various network protocols have been created for the purposes of transmitting data and voice and video information from one location to another. Among these are protocols that are intended to operate within a shared medium network. Most shared-medium network protocols are built with the expectation that collisions will occur as multiple nodes of the network contend for use of a portion of the overall network bandwidth.
A contention resolution phase normally follows a collision, and is intended to sort a single xe2x80x9cwinnerxe2x80x9d from the set of colliding nodes. There are various methods for sorting out the winners and losers of the contention phase. Several successive collisions may be incurred before a wining node is finally selected. At that point, collisions will cease temporarily, as the winning node will be the only node allowed to transmit. However, most protocols do not attempt to sort the winners from the losers in an orderly fashion, and hence, immediately after the completion of the single winning transmission, it is likely that yet another collision resolution phase will begin with the winning node immediately re-appearing in the contention process. The previous winner may well end up being the winner again, and then would be allowed to transmit a second frame before other nodes have been allowed to transmit even one frame. Over long periods of time, each node has an equal chance of becoming the winner, but for shorter periods of time, unfairness can arise, leading to large variations in average latency of delivery. The effect of network capture within the Ethernet protocol offers a common example of this sort of behavior.
More advanced network protocols force the winner of a contention resolution phase to be removed from the next contention round until each competitor for network resources has had an opportunity to transmit a frame. This approach delivers much more satisfactory performance as measured by the deviation from average latency. But even in the case where a random succession of winners may have been chosen with previous winners being denied access until all have participated, the resolution state information, specifically, the contention-resolution-derived transmission ordering, is not preserved by the network. Therefore, following each set of orderly transmissions, the network again resorts to a phase of collision resolution, where all previous winners are once again asked to re-contend for the network. Clearly, the allowance for a set of transmissions following each contention resolution phase offers much improvement over older network behaviors, yet additional improvement can be made.
The resolution of collisions imposes a direct cost upon the network. Specifically, a certain amount of network bandwidth is lost to the transmission of colliding frames and to the process of resolving the collisions. Furthermore, the resolution cycles usually employ random processes, such that there can often be a substantial time-variance in the duration of the contention resolution phase. This time-variance in the collision resolution process directly impacts the time-variance of the average frame delivery latency. With increasing demands from network users for more and more latency-sensitive data streams (e.g., real-time video and audio streams), frame delivery latency variance becomes a very important parameter of network behavior. The smaller the delivery latency variance, the better the performance of the network for the delivery of these streams, the less buffering that will be required, and the more valuable the network will be.
Some shared medium network protocols create a transmission ordering by using an n-ary tree method of collision resolution that eventually selects a series of network contention winners. A network variable is maintained by each node of the network in order to track the progress of the contention resolution mechanism. The variable indicates the current depth of the n-ary tree. It is maintained so that newly queued frames will be placed at the tail of the queue of nodes that are offering frames for transmission. This network variable resolves to zero following the complete resolution of any given network contention resolution phase. The invention improves such protocols by adding a MORE field to each outgoing frame. The MORE field instructs all receiving nodes (and the sending node) to leave the network variable for the n-ary tree at its current depth when it would otherwise have reduced the depth due to the passage of a successful transmission or reception. The MORE field is only set in outgoing frames when the currently transmitting node has another frame in its transmit queue. The conveyance of this information implies that the depth of the n-ary tree will remain the same because the removal of an entry at the head of the network queue will be countered by the addition of an entry at the tail of the queue. Because the n-ary tree resolves to a queue of singular width at the head end, entries placed at the tail of the queue by the immediately preceding transmitter are also singular in width. As a result, when provided with a steady flow of frames at each node""s transmission queue, the network behavior resolves to that of a highly ordered contention-free protocol, with the overhead and time-variance of the collision resolution process having vanished. Networks containing a mixture of nodes with empty and non-empty transmission queues show a mixed behavior, but with a general reduction in overhead due to the reduced requirement for collision resolution. Networks that have any nodes with multiple-entry transmission queues will show a benefit from the invention when the performance metrics of average latency, latency jitter and throughput are measured.
The foregoing and other features, aspects and advantages of the present invention will become more apparent from the following detailed description of the present invention when taken in conjunction with the accompanying drawings.